﻿\subsection[线程、进程的管理]{线程 \protect\footnote{ 在讨论实现时提及的线程均指内核线程。}、进程的管理 }

\subsubsection{线程调度}

内核线程在内核中是用线程控制块来表示的。
线程调度实质上就是将当前 CPU 中的执行流状态存放在 TCB 中，然后另择一个 TCB 恢复其中保存的执行流。
从概念上看，线程在某一时刻可以拥有至少五种状态：创建态、就绪态、运行态、挂起态、终止态。
创建线程后要么立即开始执行，要么暂时挂起，等待外界启动该线程。
因而从实现的角度看，实际的状态有四种：就绪态、挂起态、终止态，对应地就需要分别维护三种不同的 TCB 队列。


线程的本质是执行流，在执行用户程序的过程中一般处于用户特权级。
外部中断、用户程序异常、系统调用等事件都会导致当前执行流从用户态转入内核态。
在中断及异常处理一章中已经提及，x86 体系结构中当上述中断事件发生时，除了进行特权级切换，还将执行流被中断前的若干重要寄存器保存在栈中。
如果中断本就发生于内核态，则不进行栈的切换；若发生于用户态，除需要保存的寄存器有所不同，CPU 还会进行栈帧的切换，CPU 此时会从任务状态段（Task State Segment）中取出 \lstinline{SS0} 和 \lstinline{ESP0} 作为新的栈顶指针，而后将需要保存的寄存器存放于该栈中。


鉴于 x86 的此种特性，基于 x86 的操作系统一般为线程设置两个栈，分为位于用户空间和内核空间。
当线程运行于用户态时，内核栈中不存放任何内容。
只有当系统调用等触发中断的事件产生时，才会使用到内核栈。
内核栈一般很小，如 x86 GNU/Linux 中使用的内核栈大小只有两个页面。
引入内核栈除了区分用户数据和内核数据和避免可能的栈溢出外，还有另外一点好处：对于 CPU 而言，执行流是以寄存器中保存的值、内存中保存的数据的形态存在的。
内存中的数据由于尚未读入寄存器，因而对于 CPU 还只是无意义的字节序列。
这就导致 CPU 在执行一段指令时，并不知道这段指令究竟归属于哪个线程。
当需要进行线程切换时，首先需要明确的就是当前正在运行哪个线程。
GNU/Linux 的做法是将 \lstinline{task_struct} 信息存放于栈底 \footnote{GNU/Linux 引入更高效的内存分配器 buddy 分配器（页面分配）和 slab 分配器（内存块分配）后，改为将指向 \footnotesize\lstinline{task_struct} 的指针 \footnotesize\lstinline{thread_info} 存放于栈底。
}。
以固定占用两个页面的内核栈为例，从用户态转入内核态后，只需要将当前栈指针指向的地址与 \lstinline{0xFFFF'E000} 做与运算，将低 13 位的栈内偏移地址零，即可得到位于栈底的 TCB，进而确定当前运行的线程。

根据上述设计思想，SimpleOS 为线程设计了如下的线程控制块。

\begin{minted}[breaklines, breakautoindent=true]{cpp}
/* 
@brief 线程控制块
*/
typedef struct __ThreadControlBlock
{
    struct __ThreadControlBlock* lpPrev; /* 调度队列中的上一个线程 */
    struct __ThreadControlBlock* lpNext; /* 调度队列中的下一个线程 */
    struct __ProcessControlBlock* lpProcess; /* 线程所属的进程 */
    struct __ThreadControlBlock* lpSibling; /* 兄弟线程，同属于一个进程 */
    BOOL bIsIdle; /* 是否为空闲线程，空闲线程常驻就绪队列，在无线程可指派时上处理器运行 */
    DWORD dwProcessId; /* 所属进程 Id */
    DWORD dwThreadId; /* 线程 Id */
    LPVOID lpUserStack; /* 线程用户态堆栈 */
    LPVOID lpKernelStack; /* 线程使用的内核态堆栈，其大小固定为 8 KiB */
    DWORD dwUserStackSize; /* 线程堆栈大小 */
    LPTHREAD_START_ROUTINE lpStartAddress; /* 线程入口地址 */
    LPVOID lpParameter; /* 线程执行所需的参数 */
    DWORD dwPriority; /* 线程优先级 */
    int nTicks; /* 运行的时间片数量 */
    DWORD dwStatus; /* 线程状态 */
    IntExceptContext context; /* 线程被中断时的上下文 */
} ThreadControlBlock, *LPThreadControlBlock, *LPTCBQUEUE;
\end{minted}

线程控制块存放于线程内核栈栈底，在调度队列中，采用带头结点的双向链表结构维护线程控制块。
\lstinline{lpPrev} 和 \lstinline{lpNext} 用于在调度队列中标识一对相邻的线程。
调度器采用时间片轮转法（Round Robin，RR）每次从调度队列中取出线程 \lstinline{*g_lpReadyQueue}\lstinline{->lpNext} 并调度其上处理器运行（图 \ref{SCHEDULER_QUEUE_0} 中的 Thread \#1）。

\begin{figure}[h!]
    \Centering
    \caption{线程调度队列（一）}
    \label{SCHEDULER_QUEUE_0}
    \includegraphics[scale=0.9]{build/Paper/Assets/ThreadRelation_00.pdf}
\end{figure}

Thread \#5 从处理器上换下，保存上下文后，链接到调度队列队尾 \lstinline{*g_lpReadyQueue}\lstinline{->lpPrev}。
随后，将 Thread \#1 移出调度队列，恢复 Thread \#1 上下文，使得 Thread \#1 恢复执行（图 \ref{SCHEDULER_QUEUE_1}）。

\begin{figure}[h!]
    \Centering
    \caption{线程调度队列（二）}
    \label{SCHEDULER_QUEUE_1}
    \includegraphics[scale=0.9]{build/Paper/Assets/ThreadRelation_01.pdf}
\end{figure}

上述调度发生于内核态，中断例程使用 Thread \#5 的内核栈。
保存 Thread \#5 中断现场后，调度器在 Thread \#1 的内核栈中恢复 Thread \#1 的中断现场，将 \lstinline{SS:ESP} 切换至 Thread \#1 内核栈（此前 Thread \#5 内核栈中的内容全部丢弃）
而后由 \lstinline{iret} 指令恢复 Thread \#1 的执行（图 \ref{THREAD_SWITCH}）。

\begin{figure}[h!]
    \Centering
    \caption{线程切换}
    \label{THREAD_SWITCH}
    \includegraphics[scale=0.75]{build/Paper/Assets/ContextSwitch.pdf}
\end{figure}

调度队列中，存在特殊的空闲线程（Idle Thread），空闲线程实际上就对应于调度队列中的头结点。
当调度队列中除空闲线程外无可调度线程时，调度器将调度空闲线程上处理器运行。
空闲线程被调度时，带头结点双向链表的特性可确保空闲线程的控制块并不会从链队中移除，进而可保证空闲线程常驻调度队列，在任意时刻总是有线程在 CPU 上运行。

\subsubsection{进程资源管理}

进程是线程的容器，进程控制块中记录着进程拥有的若干线程以及诸线程需要的全局资源。
SimpleOS 中的进程控制块结构如下。

\begin{minted}[breakautoindent=true, breaklines]{cpp}
/* 进程控制块 */
typedef struct __ProcessControlBlock
{
    struct __ProcessControlBlock* lpChildProcess; /* 孩子节点 */
    struct __ProcessControlBlock* lpSiblingProcess; /* 兄弟节点 */
    struct __ThreadControlBlock* lpThreadList; /* 进程拥有的诸线程 */
    LPCSTR lpName; /* 进程名 */
    DWORD dwProcessId; /* 进程 Id */
    LPHeap lpHeap; /* 进程的堆，由各进程共享 */
    LPPageDirectoryEntry lpVirtualPageDirectory; /* 进程的页目录在主控页目录中对应的地址 */
    DWORD dwCR3; /* 进程的页表 */
} ProcessControlBlock, *LPProcessControlBlock;
\end{minted}

线程通过一条单向链表 \lstinline{lpThreadList} 管理其拥有的所有线程。
进程与进程之间还存在父子关系，当进程 Process \#0 中的某一线程调用 \lstinline{CreateProcess} 创建新进程 Process \#1 时，Process \#1 就成为 Process \#0 的子进程。
进程之间的这种关系可用树来描述，鉴于父子进程之间的一对多关系，采用兄弟描述法来刻画这样的多叉树。
进而，进程与线程、进程与进程之间就形成了如图 \ref{PROCESS_THREAD_TOPO} 的拓扑结构。

\begin{figure}[h!]
    \Centering
    \caption{进程、线程的拓扑结构}
    \label{PROCESS_THREAD_TOPO}
    \includegraphics[scale=0.75]{build/Paper/Assets/ProcessThreadRelation.pdf}
\end{figure}
